// ret  =  next  + prev
// f(n) = f(n-1) + f(n-2); => 状态变更(转移)的公式
export function fibonacci(n: number): number {
  if (n === 1 || n === 2) {
    return n;
  }
  let prev = 1;
  let ret = 0;
  let next = 2;
  for (let i = 3; i < n + 1; i++) {
    // 状态转移
    ret = next + prev;
    prev = next;
    next = ret;
  }

  return ret;
}

// 三角形的最小路径和
/*

              2
            3   4
           6  5  7
          4  1  8  3
  以上三角形由一连串的数字构成，要求从顶点 2 开始走到最底下边的最短路径，每次只能向当前节点下面的两个节点走，如 3 可以向 6 或 5 走，不能直接走到 7。
*/

/*
  NOTE:
  使用 二维数组来表示矩阵地图， 如果我们自底向上去思考， 如果要求 2 - 底部的最小的路径， 那么我们可以看到 倒数第二层到底部的最小路径， 因为最后一层到底部的路径就是本身的值
  那么倒数第二层到底部的最小就是 6 -> 4 和 6 -> 1 => 得到 7； 5 -> 1 和 5 -> 8 得到 6 ； 7 -> 8 和 7 -> 3 得到 10 => 第三层变为 7 ， 6 ， 10
  那么再看第三层到第二层的最短的距离： 3 -> 7 和 3 -> 6 得到 9 ； 4 -> 6 和 4 -> 10 得到 10， 第二层变为=> 9 ， 10
  那么这个时候看第一层到第二层的距离： 2 -> 9 和 2 => 10 得到 11， 那么自然就是 11 最短， 我们只需要记录到这些过程中经过的路径

  NOTE: 那么就是说如果要求该 节点到底部的路径最短，那么我们只需要要求改节点的左右两个节点到达底部的路径最短
  DP[i,j] = min(DP[i+1, j], DP[i+1, j+1]) + triangle[i,j],
*/

// 这里只处理三角型的地图
const triangle: number[][] = [
  [2, 0, 0, 0],
  [3, 4, 0, 0],
  [6, 5, 7, 0],
  [4, 1, 8, 3],
];

export function minPath() {
  let row = triangle.length;
  const paths = [];
  const mini = triangle[row - 1]; // 初始是最后一层， 保存每一层的变化，得到最上面的一层的数值
  let min = mini[0];
  let minIndex = 0;
  for (let i = 0; i < mini.length; i++) {
    const item = mini[i];
    if (item < min && item !== 0) {
      min = item;
      minIndex = i;
    }
  }
  paths.unshift(minIndex);

  for (let i = row - 2; i >= 0; i--) {
    // 从倒数第二层开始计算
    for (let j = 0; j < triangle[i].length; j++) {
      const self = triangle[i][j];
      if (self === 0) {
        mini[j] = 0; // 避免上一层的数据留到下一层
        continue;
      }
      mini[j] = self + Math.min(mini[j], mini[j + 1]);
    }
    min = mini[0];
    minIndex = 0;
    for (let i = 0; i < mini.length; i++) {
      const item = mini[i];
      if (item < min && item !== 0) {
        min = item;
        minIndex = i;
      }
    }
    paths.unshift(minIndex);
  }
  return [mini[0], paths];
}

console.log(minPath());


// 进阶：凑零钱

/*

*/